LCA in Binary Tree
問題概要
二分木における最小共通祖先、LCA(Lowest Common Ancestor)を探せという問題 二分木における任意のノードp, qが与えられる
ルートノードから最も遠いp, qの共通の親ノードを見つけよ、というもの
結構難しかったnixii.icon
方針思いついた後も細かいエラーが発生して3~4時間かけての自力ACだった
(追記)別解がスマートなので参考にするならこっち
難しいというより、簡単な問題なのに難しく考えすぎてた
以下、自分で考えた解法
inorder, postorderかinorder, preorderで巡回した配列を用意
pとqの親ノード(もしくはp, q自身のノード)を探せば良さそう
という方針を思いついた
計算量はO(N^2)
具体的には
まずinorder巡回による値の配列insとpostorder巡回による値の配列postsを用意
insにおけるp, qの閉区間_insを用意
ちなみに
閉区間とは範囲を指定する値自身を含む区間であり、[p, q]と表現
開区間とは範囲を指定する値自身を含まない区間であり、(p, q)と表現
プログラミングでよく聞く半開区間は片方だけ閉区間、もう片方は開区間となってる区間でよく重宝される
[p, q)なら、p~qまでの値のうちpは含むがqは含まない区間を指す
postsをループで走査し、値が_insに含まれている最後の値であれば、その値をもつノードが答えとなる
理由
insの任意の値を注目した時、その左右に存在する値は、実際の二分木でも必ず注目した値のノードの左右に分布する
つまり、p, qの親ノードの値は必ず_insにあり、かつその値は帰りがけ順に巡回して「_insに含まれる値として最後に出会う」値となる
code:solution.cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// create inorder and postorder traversed vectors
vector<int> ins = {};
vector<int> posts = {};
inorder_traverse(root, ins);
postorder_traverse(root, posts);
int ins_begin = -1;
int ins_end;
for (int i=0; i<ins.size(); i++) {
if (ins_begin < 0 && (insi == p->val || insi == q->val)) ins_begin = i; else if (insi == p->val || insi == q->val) { if (ins_begin > i) {
ins_end = ins_begin;
ins_begin = i;
}
else ins_end = i;
}
}
vector<int> _ins = {};
for (int i=ins_begin; i<=ins_end; i++) _ins.push_back(insi); if (ins_begin > ins_end) _ins = ins;
int posts_idx = -1;
for (int i=0; i<posts.size(); i++) {
if ((postsi == p->val || postsi == q->val) && posts_idx < i) posts_idx = i; }
int ans;
TreeNode* ans_node;
vector<TreeNode*> nodes = {};
traverse(root, nodes);
for (int n : posts) {
if (vec_find(_ins, n)) {
for (TreeNode* node : nodes) if (node->val == n) ans_node = node;
}
}
return ans_node;
}
void inorder_traverse(TreeNode* node, vector<int>& ins) {
if (node) {
if (node->left) inorder_traverse(node->left, ins);
ins.push_back(node->val);
if (node->right) inorder_traverse(node->right, ins);
};
}
void postorder_traverse(TreeNode* node, vector<int>& posts) {
if (node) {
if (node->left) postorder_traverse(node->left, posts);
if (node->right) postorder_traverse(node->right, posts);
posts.push_back(node->val);
};
}
void traverse(TreeNode* node, vector<TreeNode*>& nodes) {
if (node) {
nodes.push_back(node);
traverse(node->left, nodes);
traverse(node->right, nodes);
}
}
bool vec_find(vector<int> vec, int val) {
bool flag = false;
for (int n : vec) if (n == val) flag = true;
return flag;
}
};